package com.lw.leetcode.bit.b;

/**
 * Created with IntelliJ IDEA.
 * 1415. 长度为 n 的开心字符串中字典序第 k 小的字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/6 13:11
 */
public class GetHappyString {

    public static void main(String[] args) {
        GetHappyString test = new GetHappyString();

        // cab
//        int n = 3;
//        int k = 9;

        // abacbabacb
        int n = 10;
        int k = 100;

        // c
//        int n = 1;
//        int k = 3;

        String happyString = test.getHappyString(n, k);
        System.out.println(happyString);
    }

    public String getHappyString(int n, int k) {
        int t = 1 << (n - 1);
        int c = t * 3;
        if (c < k) {
            return "";
        }
        char[] arr = new char[n];
        arr[0] = (char) ((k - 1) / t + 'a');
        k = k % t - 1;
        char[] chars = {'b', 'c', 'a', 'c', 'a', 'b'};
        for (int i = n - 1; i > 0; i--) {
            int index = ((arr[n - i - 1] - 'a') << 1) + ((k >> (i - 1)) & 1);
            arr[n - i] = chars[index];
        }
        return String.valueOf(arr);
    }

}
